import java.util.*;

public class Test {
    // 题目1 ：整数转罗马数字
    int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    String[] romans = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    public String intToRoman(int num) {
        int n = values.length;
        StringBuilder res = new StringBuilder();
        for(int i = 0; i < n; i++){
            int value = values[i];
            String roman = romans[i];
            while(num >= value){
                res.append(roman);
                num -= value;
            }
        }
        return res.toString();
    }

    // 题目2：杨辉三角
    public List<List<Integer>> generate1(int numRows) {
        List<List<Integer>> lists = new LinkedList<>();
        for(int i = 0; i < numRows; i++){
            List<Integer> list = new LinkedList<>();
            for(int j = 0; j <= i; j++){
                if(j == 0 ||  j == i){
                    list.add(1);
                }else{
                    List<Integer> temp = lists.get(i - 1);
                    list.add(temp.get(j) + temp.get(j - 1));
                }
            }
            lists.add(list);
        }
        return lists;
    }

    // 第二种做法
    // 前一行的杨辉三角，从头到尾，两两相加，得到下一行的数字。头尾再加 1 即可。
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> lists = new LinkedList<>();
        for(int i = 0; i < numRows; i++){
            List<Integer> list = new LinkedList<>();
            list.add(1);
            if(i - 1 >= 0){
                List<Integer> temp = lists.get(i - 1);
                int sz = temp.size();
                for(int j = 0; j < sz - 1; j++){
                    list.add(temp.get(j) + temp.get(j + 1));
                }
                list.add(1);
            }
            lists.add(list);
        }
        return lists;
    }


    // 题目3： 杨辉三角 II
    // 用两个列表来回倒
    public List<Integer> getRow(int rowIndex) {
        List<Integer> list = new LinkedList<>();
        for(int i = 0; i <= rowIndex; i++){
            List<Integer> temp = new LinkedList<>();
            for(int j = 0; j <= i; j++){
                if(j == 0 || j == i){
                    temp.add(1);
                }else{
                    temp.add(list.get(j) + list.get(j - 1));
                }
            }
            list = temp;
        }
        return list;
    }

    // 题目4：最小体力消耗路径
    // 图论题，但是边权值不为 1
    // 这个题是 dp 和 bfs 的结合体
    public static void main1(String[] args) {
        int[][] dp = new int[4][4];
        for(int i = 0; i < 4; i++){
            Arrays.fill(dp[i], 1);
        }
    }

    public int minimumEffortPath(int[][] heights) {
        int m = heights.length;
        int n = heights[0].length;
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};
        int[][] dp = new int[m][n];
        for(int i = 0; i < m; i++){
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[0][0] = 0;
        PriorityQueue<int[]> q = new PriorityQueue<>(new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                return a[2] - b[2];
            }
        });
        q.offer(new int[]{0, 0, 0});
        boolean[][] vis = new boolean[m][n];

        while(!q.isEmpty()){
            int[] t = q.poll();
            int a = t[0], b = t[1], c = t[2];

            if(vis[a][b]){
                continue;
            }

            if(a == m - 1 && b == n - 1){
                break;
            }
            vis[a][b] = true;
            for(int i = 0; i < 4; i++){
                int x = a + dx[i], y = b + dy[i];
                if(x >= 0 && x < m && y >= 0 && y < n && Math.max(c, Math.abs(heights[a][b] - heights[x][y])) < dp[x][y]){
                    dp[x][y] = Math.max(c, Math.abs(heights[a][b] - heights[x][y]));
                    q.offer(new int[]{x, y, dp[x][y]});
                }
            }
        }
        return dp[m - 1][n - 1];
    }

    // 题目5：相同的树
    public static boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null){
            return true;
        }
        if( q == null || p == null  || p.val != q.val){
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    public static void main2(String[] args) {
        TreeNode h1 = new TreeNode(1);
        h1.left = new TreeNode(2);
        h1.right = new TreeNode(3);
        TreeNode h2 = new TreeNode(1);
        h2.left = new TreeNode(2);
        h2.right = new TreeNode(3);

        boolean res = isSameTree(h1, h2);
        System.out.println(res);
    }

    // 题目6：判别首字母缩略词
    public boolean isAcronym1(List<String> words, String s) {
        StringBuilder res = new StringBuilder();
        for(String ss : words){
            res.append(ss.charAt(0));
        }
        return res.toString().equals(s);
    }

    public boolean isAcronym(List<String> words, String s) {
        if(words.size() != s.length()){
            return false;
        }

        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) != words.get(i).charAt(0) ){
                return false;
            }
        }
        return true;
    }

    // 题目7：合并两个有序链表
    // 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummyNode = new ListNode(-1);
        ListNode cur = dummyNode;
        while(list1 != null && list2 != null){
            if(list1.val <= list2.val){
                cur.next = list1;
                cur = list1;
                list1 = list1.next;
            }else{
                cur.next = list2;
                cur = list2;
                list2 = list2.next;
            }
        }
        if(list1 != null){
            cur.next = list1;
        }
        if(list2 != null){
            cur.next = list2;
        }
        return dummyNode.next;
    }




}
